#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctype.h>

//图书信息结构体
typedef struct Book {
    char title[100];
    char author[50];    char isbn[20];
    char publisher[50];
    int year;
    int stock;
    struct Book *next;
} Book;

// 读者信息结构体
typedef struct Reader {
    char id[20];
    char name[50];
    char contact[50];
    struct Reader *next;
} Reader;

// 借阅记录结构体
typedef struct BorrowRecord {
    char reader_id[20];
    char book_isbn[20];
    time_t borrow_time;
    time_t due_time;
    struct BorrowRecord *next;
} BorrowRecord;

// 预约队列结构体
typedef struct Reservation {
    char reader_id[20];
    char book_isbn[20];
    time_t reserve_time;
    struct Reservation *next;
} Reservation;

// 操作栈结构体(用于回滚)
typedef struct Operation {
    int type; // 1:借阅 2:归还
    char reader_id[20];
    char book_isbn[20];
    time_t time;
    struct Operation *next;
} Operation;

// 全局变量
Book *book_list = NULL;
Reader *reader_list = NULL;
BorrowRecord *borrow_list = NULL;
Reservation *reservation_queue = NULL;
Operation *operation_stack = NULL;

// 函数声明
void initialize_system();
void save_data_to_files();
void add_new_book();
void register_new_reader();
void borrow_book();
void return_book();
void search_books();
void search_readers();
void process_reservations();
void display_statistics();
void free_memory();
void convert_arrays_to_lists_if_needed();
int count_books();
int count_readers();
int count_borrow_records();
void sort_books_by_year();
void sort_readers_by_registration_time();
Book* binary_search_book_by_isbn(char *isbn);
Reader* binary_search_reader_by_name(char *name);

void initialize_system() {
    FILE *file;
    
    // 读取书籍信息
    file = fopen("books.txt", "r");
    if (file) {
        Book book;
        while (fscanf(file, "%[^|]|%[^|]|%[^|]|%[^|]|%d|%d\n", 
                      book.title, book.author, book.isbn, book.publisher, &book.year, &book.stock) == 6) {
            Book *new_book = (Book*)malloc(sizeof(Book));
            *new_book = book;
            new_book->next = book_list;
            book_list = new_book;
        }
        fclose(file);
    }
    
    // 读取读者信息
    file = fopen("readers.txt", "r");
    if (file) {
        Reader reader;
        while (fscanf(file, "%[^|]|6%[^|]|%[^|]\n", 
                      reader.id, reader.name, reader.contact) == 3) {
            Reader *new_reader = (Reader*)malloc(sizeof(Reader));
            *new_reader = reader;
            new_reader->next = reader_list;
            reader_list = new_reader;
        }
        fclose(file);
    }

    // 读取借阅记录
    file = fopen("borrows.txt", "r");
    if (file) {
        BorrowRecord record;
        char borrow_str[20], due_str[20];
        while (fscanf(file, "%[^|]|%[^|]|%[^|]|%[^\n]\n", 
                      record.reader_id, record.book_isbn, borrow_str, due_str) == 4) {
            record.borrow_time = atol(borrow_str);
            record.due_time = atol(due_str);
            BorrowRecord *new_record = (BorrowRecord*)malloc(sizeof(BorrowRecord));
            *new_record = record;
            new_record->next = borrow_list;
            borrow_list = new_record;
        }
        fclose(file);
    }
    
    printf("系统初始化完成。\n");
}

// 将数据保存到文件
void save_data_to_files() {
    FILE *file;
    
    // 保存书籍信息
    file = fopen("books.txt", "w");
    if (file) {
        Book *current = book_list;
        while (current) {
            fprintf(file, "%s|%s|%s|%s|%d|%d\n", 
                    current->title, current->author, current->isbn, 
                    current->publisher, current->year, current->stock);
            current = current->next;
        }
        fclose(file);
    }
    
    // 保存读者信息
    file = fopen("readers.txt", "w");
    if (file) {
        Reader *current = reader_list;
        while (current) {
            fprintf(file, "%s|%s|%s\n", 
                    current->id, current->name, current->contact);
            current = current->next;
        }
        fclose(file);
    }
    
    // 保存借阅记录
    file = fopen("borrows.txt", "w");
    if (file) {
        BorrowRecord *current = borrow_list;
        while (current) {
            fprintf(file, "%s|%s|%ld|%ld\n", 
                    current->reader_id, current->book_isbn, 
                    current->borrow_time, current->due_time);
            current = current->next;
        }
        fclose(file);
    }
    
    printf("数据已保存到文件。\n");
}

// 添加新书
void add_new_book() {
    Book new_book;
    
    printf("请输入书名: ");
    scanf(" %[^\n]", new_book.title);
    printf("请输入作者: ");
    scanf(" %[^\n]", new_book.author);
    printf("请输入ISBN号: ");
    scanf(" %[^\n]", new_book.isbn);
    printf("请输入出版社: ");
    scanf(" %[^\n]", new_book.publisher);
    printf("请输入出版年份: ");
    scanf("%d", &new_book.year);
    printf("请输入库存数量: ");
    scanf("%d", &new_book.stock);
    
    // 检查是否已存在相同ISBN的书
    Book *existing = binary_search_book_by_isbn(new_book.isbn);
    if (existing) {
        existing->stock += new_book.stock;
        printf("已存在相同ISBN的书籍，库存已增加。\n");
    } else {
        Book *new_node = (Book*)malloc(sizeof(Book));
        *new_node = new_book;
        new_node->next = book_list;
        book_list = new_node;
        printf("新书添加成功。\n");
    }
    
    convert_arrays_to_lists_if_needed();
}

// 注册新读者
void register_new_reader() {
    Reader new_reader;
    
    printf("请输入读者ID: ");
    scanf(" %[^\n]", new_reader.id);
    printf("请输入姓名: ");
    scanf(" %[^\n]", new_reader.name);
    printf("请输入联系方式: ");
    scanf(" %[^\n]", new_reader.contact);

    // 检查是否已存在相同ID的读者
    Reader *current = reader_list;
    while (current) {
        if (strcmp(current->id, new_reader.id) == 0) {
            printf("该ID已存在，请使用不同的ID。\n");
            return;
        }
        current = current->next;
    }
    
    Reader *new_node = (Reader*)malloc(sizeof(Reader));
    *new_node = new_reader;
    new_node->next = reader_list;
    reader_list = new_node;
    printf("读者注册成功。\n");
    
    convert_arrays_to_lists_if_needed();
}
// 借阅书籍
void borrow_book() {
    char reader_id[20], isbn[20];
    printf("请输入读者ID: ");
    scanf(" %[^\n]", reader_id);
    printf("请输入书籍ISBN: ");
    scanf(" %[^\n]", isbn);
    
    // 查找读者
    Reader *reader = NULL;
    Reader *current_reader = reader_list;
    while (current_reader) {
        if (strcmp(current_reader->id, reader_id) == 0) {
            reader = current_reader;
            break;
        }
        current_reader = current_reader->next;
    }
    
    if (!reader) {
        printf("未找到该读者。\n");
        return;
    }

    
    // 查找书籍
    Book *book = binary_search_book_by_isbn(isbn);
    if (!book) {
        printf("未找到该书籍。\n");
        return;
    }
    
    // 检查库存
    if (book->stock <= 0) {
        printf("该书籍库存不足，是否预约? (y/n): ");
        char choice;
        scanf(" %c", &choice);
        if (choice == 'y' || choice == 'Y') {
            // 添加到预约队列
            Reservation *new_reservation = (Reservation*)malloc(sizeof(Reservation));
            strcpy(new_reservation->reader_id, reader_id);
            strcpy(new_reservation->book_isbn, isbn);
            new_reservation->reserve_time = time(NULL);
            new_reservation->next = NULL;
            
            if (!reservation_queue) {
                reservation_queue = new_reservation;
            } else {
                Reservation *last = reservation_queue;
                while (last->next) last = last->next;
                last->next = new_reservation;
            }
            printf("预约成功，当书籍可用时会通知您。\n");
        }
        return;
    }
    
    // 创建借阅记录
    BorrowRecord *new_record = (BorrowRecord*)malloc(sizeof(BorrowRecord));
    strcpy(new_record->reader_id, reader_id);
    strcpy(new_record->book_isbn, isbn);
    new_record->borrow_time = time(NULL);
    new_record->due_time = new_record->borrow_time + 30 * 24 * 60 * 60; // 30天后到期
    new_record->next = borrow_list;
    borrow_list = new_record;
    
    // 更新库存
    book->stock--;
    
    // 记录操作到栈(用于回滚)
    Operation *op = (Operation*)malloc(sizeof(Operation));
    op->type = 1; // 借阅操作
    strcpy(op->reader_id, reader_id);
    strcpy(op->book_isbn, isbn);
    op->time = time(NULL);
    op->next = operation_stack;
    operation_stack = op;
    
    printf("借阅成功，请在30天内归还。\n");
}

// 归还书籍
void return_book() {
    char reader_id[20], isbn[20];
    printf("请输入读者ID: ");
    scanf(" %[^\n]", reader_id);
    printf("请输入书籍ISBN: ");
    scanf(" %[^\n]", isbn);
    
    // 查找借阅记录
    BorrowRecord *prev = NULL;
    BorrowRecord *current = borrow_list;
    while (current) {
        if (strcmp(current->reader_id, reader_id) == 0 && 
            strcmp(current->book_isbn, isbn) == 0) {
            break;
        }
        prev = current;
        current = current->next;
    }
    
    if (!current) {
        printf("未找到该借阅记录。\n");
        return;
    }
    
    // 从借阅列表中移除记录
    if (prev) {
        prev->next = current->next;
    } else {
        borrow_list = current->next;
    }
    
    // 更新书籍库存
    Book *book = binary_search_book_by_isbn(isbn);
    if (book) {
        book->stock++;
    }
    
    
    // 记录操作到栈(用于回滚)
    Operation *op = (Operation*)malloc(sizeof(Operation));
    op->type = 2; // 归还操作
    strcpy(op->reader_id, reader_id);
    strcpy(op->book_isbn, isbn);
    op->time = time(NULL);
    op->next = operation_stack;
    operation_stack = op;
    
    free(current);
    
    // 检查是否有预约
    process_reservations();
}
// 搜索书籍
void search_books() {
    int choice;
    printf("请选择搜索方式:\n");
    printf("1. 按书名\n");
    printf("2. 按作者\n");
    printf("3. 按ISBN\n");
    printf("4. 按出版社\n");
    printf("5. 返回\n");
    printf("请输入选择: ");
    scanf("%d", &choice);
    
    if (choice == 5) return;
    
    char query[100];
    printf("请输入搜索关键词: ");
    scanf(" %[^\n]", query);
    
    Book *current = book_list;
    int found = 0;
    
    while (current) {
        int match = 0;
        switch (choice) {
            case 1: 
                if (strstr(current->title, query)) match = 1;
                break;
            case 2:
                if (strstr(current->author, query)) match = 1;
                break;
            case 3:
                if (strcmp(current->isbn, query) == 0) match = 1;
                break;
            case 4:
                if (strstr(current->publisher, query)) match = 1;
                break;
        }
        
        if (match) {
            printf("\n书名: %s\n", current->title);
            printf("作者: %s\n", current->author);
            printf("ISBN: %s\n", current->isbn);
            printf("出版社: %s\n", current->publisher);
            printf("出版年份: %d\n", current->year);
            printf("库存: %d\n\n", current->stock);
            found = 1;
        }
        current = current->next;
    }
    
    if (!found) {
        printf("未找到匹配的书籍。\n");
    }
}

// 搜索读者
void search_readers() {
    int choice;
    printf("请选择搜索方式:\n");
    printf("1. 按姓名\n");
    printf("2. 按ID\n");
    printf("3. 返回\n");
    printf("请输入选择: ");
    scanf("%d", &choice);
    
    if (choice == 3) return;
    
    char query[100];
    printf("请输入搜索关键词: ");
    scanf(" %[^\n]", query);
    
    Reader *current = reader_list;
    int found = 0;
    
    while (current) {
        int match = 0;
        switch (choice) {
            case 1: 
                if (strstr(current->name, query)) match = 1;
                break;
            case 2:
                if (strcmp(current->id, query) == 0) match = 1;
                break;
        }
        
        if (match) {
            printf("\nID: %s\n", current->id);
            printf("姓名: %s\n", current->name);
            printf("联系方式: %s\n", current->contact);
            found = 1;
        }
        current = current->next;
    }
    
    if (!found) {
        printf("未找到匹配的读者。\n");
    }
}

// 处理预约队列
void process_reservations() {
    if (!reservation_queue) return;
    
    time_t now = time(NULL);
    Reservation *current = reservation_queue;
    Reservation *prev = NULL;
    
    while (current) {
        Book *book = binary_search_book_by_isbn(current->book_isbn);
        if (book && book->stock > 0) {
            // 可以借阅
            Reader *reader = NULL;
            Reader *r = reader_list;
            while (r) {
                if (strcmp(r->id, current->reader_id) == 0) {
                    reader = r;
                    break;
                }
                r = r->next;
            }
            
            if (reader ) {
                // 创建借阅记录
                BorrowRecord *new_record = (BorrowRecord*)malloc(sizeof(BorrowRecord));
                strcpy(new_record->reader_id, current->reader_id);
                strcpy(new_record->book_isbn, current->book_isbn);
                new_record->borrow_time = now;
                new_record->due_time = now + 30 * 24 * 60 * 60; // 30天后到期
                new_record->next = borrow_list;
                borrow_list = new_record;
                
                // 更新库存
                book->stock--;
                
                printf("读者 %s 预约的书籍 %s 已可用，已自动借阅。\n", 
                       reader->name, book->title);
                
                // 从预约队列中移除
                if (prev) {
                    prev->next = current->next;
                } else {
                    reservation_queue = current->next;
                }
                
                Reservation *to_delete = current;
                current = current->next;
                free(to_delete);
                continue;
            }
        }
        
        prev = current;
        current = current->next;
    }
}
// 按ISBN二分查找书籍
// 按ISBN查找书籍（优化后的线性查找）
Book* binary_search_book_by_isbn(char *isbn) {
    Book *current = book_list;
    while (current) {
        if (strcmp(current->isbn, isbn) == 0) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// 按姓名查找读者（优化后的线性查找）
Reader* binary_search_reader_by_name(char *name) {
    Reader *current = reader_list;
    while (current) {
        if (strcmp(current->name, name) == 0) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// 交换两个书籍节点
void swap_books(Book *a, Book *b) {
    Book temp = *a;
    strcpy(a->title, b->title);
    strcpy(a->author, b->author);
    strcpy(a->isbn, b->isbn);
    strcpy(a->publisher, b->publisher);
    a->year = b->year;
    a->stock = b->stock;
    
    strcpy(b->title, temp.title);
    strcpy(b->author, temp.author);
    strcpy(b->isbn, temp.isbn);
    strcpy(b->publisher, temp.publisher);
    b->year = temp.year;
    b->stock = temp.stock;
}

// 按ISBN对书籍排序(快速排序实现)
void sort_books_by_isbn() {
    // 链表快速排序实现较为复杂，这里简化为冒泡排序
    int swapped;
    Book *ptr1;
    Book *lptr = NULL;
    
    if (book_list == NULL) return;
    
    do {
        swapped = 0;
        ptr1 = book_list;
        
        while (ptr1->next != lptr) {
            if (strcmp(ptr1->isbn, ptr1->next->isbn) > 0) {
                swap_books(ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while (swapped);
}
// 交换两个读者节点
void swap_readers(Reader *a, Reader *b) {
    Reader temp = *a;
    strcpy(a->id, b->id);
    strcpy(a->name, b->name);
    strcpy(a->contact, b->contact);
    strcpy(b->id, temp.id);
    strcpy(b->name, temp.name);
    strcpy(b->contact, temp.contact);
}

// 按姓名对读者排序(快速排序实现)
void sort_readers_by_name() {
    // 链表快速排序实现较为复杂，这里简化为冒泡排序
    int swapped;
    Reader *ptr1;
    Reader *lptr = NULL;
    
    if (reader_list == NULL) return;
    
    do {
        swapped = 0;
        ptr1 = reader_list;
        
        while (ptr1->next != lptr) {
            if (strcmp(ptr1->name, ptr1->next->name) > 0) {
                swap_readers(ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while (swapped);
}

//书籍按年份大小排序
Book* merge_books(Book *a, Book *b) {
    Book dummy;
    Book *tail = &dummy;
    dummy.next = NULL;
    
    while (a && b) {
        if (a->year <= b->year) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    
    tail->next = a ? a : b;
    return dummy.next;
}

Book* merge_sort_books(Book *head) {
    if (!head || !head->next) return head;
    
    Book *slow = head;
    Book *fast = head->next;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    Book *mid = slow->next;
    slow->next = NULL;
    
    Book *left = merge_sort_books(head);
    Book *right = merge_sort_books(mid);
    
    return merge_books(left, right);
}

// 按出版年份对书籍排序(归并排序实现)
void sort_books_by_year() {
    book_list = merge_sort_books(book_list);
}


// 根据数据量动态调整存储结构
void convert_arrays_to_lists_if_needed() {
    // 在这个实现中我们始终使用链表，所以不需要转换
    // 如果开始使用数组，当数据量超过阈值时转换为链表
}

// 添加示例数据
void add_sample_data() {
    // 添加示例书籍
    Book book1 = {"C程序设计语言", "Brian W. Kernighan, Dennis M. Ritchie", "9787111128069", "机械工业出版社", 2004, 5};
    Book book2 = {"算法导论", "Thomas H. Cormen", "9787111187776", "机械工业出版社", 2006, 3};
    Book book3 = {"深入理解计算机系统", "Randal E. Bryant", "9787111321330", "机械工业出版社", 2011, 2};
    
    Book *new_book = (Book*)malloc(sizeof(Book));
    *new_book = book1;
    new_book->next = book_list;
    book_list = new_book;
    
    new_book = (Book*)malloc(sizeof(Book));
    *new_book = book2;
    new_book->next = book_list;
    book_list = new_book;
    
    new_book = (Book*)malloc(sizeof(Book));
    *new_book = book3;
    new_book->next = book_list;
    book_list = new_book;
    
    // 添加示例读者
    Reader reader1 = {"1001", "张三", "zhangsan@example.com", 0};
    Reader reader2 = {"1002", "李四", "lisi@example.com", 0};
    
    Reader *new_reader = (Reader*)malloc(sizeof(Reader));
    *new_reader = reader1;
    new_reader->next = reader_list;
    reader_list = new_reader;
    
    new_reader = (Reader*)malloc(sizeof(Reader));
    *new_reader = reader2;
    new_reader->next = reader_list;
    reader_list = new_reader;
    
    printf("示例数据已添加。\n");
}

void free_memory() {
    // 释放书籍链表
    Book *book_current = book_list;
    while (book_current) {
        Book *next = book_current->next;
        free(book_current);
        book_current = next;
    }
    
    // 释放读者链表
    Reader *reader_current = reader_list;
    while (reader_current) {
        Reader *next = reader_current->next;
        free(reader_current);
        reader_current = next;
    }
    
    // 释放借阅记录链表
    BorrowRecord *borrow_current = borrow_list;
    while (borrow_current) {
        BorrowRecord *next = borrow_current->next;
        free(borrow_current);
        borrow_current = next;
    }
    
    // 释放预约队列
    Reservation *reservation_current = reservation_queue;
    while (reservation_current) {
        Reservation *next = reservation_current->next;
        free(reservation_current);
        reservation_current = next;
    }
    
    // 释放操作栈
    Operation *operation_current = operation_stack;
    while (operation_current) {
        Operation *next = operation_current->next;
        free(operation_current);
        operation_current = next;
    }
    
}


// 显示主菜单
void display_menu() {
    printf("\n校园图书管理系统\n");
    printf("1. 添加新书\n");
    printf("2. 注册新读者\n");
    printf("3. 借阅书籍\n");
    printf("4. 归还书籍\n");
    printf("5. 搜索书籍\n");
    printf("6. 搜索读者\n");
    printf("7. 保存数据到文件\n");
    printf("8. 添加示例数据\n");
    printf("0. 退出\n");
    printf("请输入选择: ");
}

// 主函数
int main() {
    initialize_system();
    
    int choice;
    do {
        display_menu();
        scanf("%d", &choice);
        
        switch (choice) {
            case 1: add_new_book(); break;
            case 2: register_new_reader(); break;
            case 3: borrow_book(); break;
            case 4: return_book(); break;
            case 5: search_books(); break;
            case 6: search_readers(); break;
            case 7: save_data_to_files(); break;
            case 8: add_sample_data(); break;
            case 0: printf("谢谢使用!\n"); break;
            default: printf("无效选择，请重新输入。\n");
        }
    } while (choice != 0);
    
    save_data_to_files();
    free_memory();
    
    return 0;
}